home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / editors / emacs / xemacs / xemacs-1.004 / xemacs-1 / xemacs-19.13 / src / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-06-06  |  11.8 KB  |  490 lines
  1. /* Hash tables.
  2.    Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc.
  3.  
  4. This file is part of XEmacs.
  5.  
  6. XEmacs is free software; you can redistribute it and/or modify it
  7. under the terms of the GNU General Public License as published by the
  8. Free Software Foundation; either version 2, or (at your option) any
  9. later version.
  10.  
  11. XEmacs is distributed in the hope that it will be useful, but WITHOUT
  12. ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13. FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14. for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with XEmacs; see the file COPYING.  If not, write to the Free
  18. Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20. /* Synched up with: Not in FSF. */
  21.  
  22. #ifdef emacs
  23. #include <config.h>
  24. #include "lisp.h"
  25.  
  26. #define NULL_ENTRY (LISP_TO_VOID (Qnil))
  27.  
  28. #else /* !emacs */
  29.  
  30. #define NULL_ENTRY ((void *) 1)
  31.  
  32. #endif /* !emacs */
  33.  
  34. #include <string.h>
  35. #include "hash.h"
  36. #include "elhash.h"
  37.  
  38. static CONST int 
  39. primes []={
  40.   13,
  41.   29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 
  42.   761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 
  43.   8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 
  44.   62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 
  45.   389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319,
  46.   2009191, 2411033, 2893249
  47. };
  48.  
  49. /* strings code */
  50.  
  51. /* from base/generic-hash.cc, and hence from Dragon book, p436 */
  52. unsigned long
  53. string_hash (CONST void *xv)
  54. { 
  55.   unsigned int h = 0;
  56.   unsigned int g;
  57.   unsigned CONST char *x = (unsigned CONST char *) xv;
  58.  
  59.   if (!x) return 0;
  60.  
  61.   while (*x != 0)
  62.     {
  63.       h = (h << 4) + *x++;
  64.       if ((g = h & 0xf0000000) != 0)
  65.     h = (h ^ (g >> 24)) ^ g;
  66.     }
  67.  
  68.   return h;
  69. }
  70.  
  71. unsigned long
  72. memory_hash (CONST void *xv, int size)
  73. { 
  74.   unsigned int h = 0;
  75.   unsigned int g;
  76.   unsigned CONST char *x = (unsigned CONST char *) xv;
  77.  
  78.   if (!x) return 0;
  79.  
  80.   while (size > 0)
  81.     {
  82.       h = (h << 4) + *x++;
  83.       if ((g = h & 0xf0000000) != 0)
  84.     h = (h ^ (g >> 24)) ^ g;
  85.       size--;
  86.     }
  87.  
  88.   return h;
  89. }
  90.  
  91. static int 
  92. string_eq (CONST void *st1v, CONST void *st2v)
  93. {
  94.   CONST char *st1 = (CONST char *)st1v;
  95.   CONST char *st2 = (CONST char *)st2v;
  96.  
  97.   if (!st1)
  98.     return (st2)?0:1;
  99.   else if (!st2)
  100.     return 0;
  101.   else
  102.     return !strcmp (st1, st2);
  103. }
  104.  
  105.  
  106. static unsigned int 
  107. prime_size (unsigned int size)
  108. {
  109.   unsigned int i;
  110.   CONST int lim = countof (primes);
  111.   for (i = 0; i < lim; i++)
  112.     if (size <= primes [i]) return primes [i];
  113.   return primes [lim - 1];
  114. }
  115.  
  116. static void rehash (hentry *harray, c_hashtable ht, unsigned int size);
  117.  
  118. #define KEYS_DIFFER_P(old, new, testfun) \
  119.   ((testfun)?(((old) == (new))?0:(!(testfun ((old), new)))):((old) != (new)))
  120.  
  121. CONST void *
  122. gethash (CONST void *key, c_hashtable hash, CONST void **ret_value)
  123. {
  124.   hentry *harray = hash->harray;
  125.   int (*test_function)() = hash->test_function;
  126.   unsigned int hsize = hash->size;
  127.   unsigned int hcode_initial = 
  128.     (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
  129.   unsigned int hcode = hcode_initial % hsize;
  130.   hentry *e = &harray [hcode];
  131.   CONST void *e_key = e->key;
  132.  
  133.   if (!key) 
  134.     {
  135.       *ret_value = hash->zero_entry;
  136.       return (void *) hash->zero_set;
  137.     }
  138.     
  139.   if ((e_key)?
  140.       (KEYS_DIFFER_P (e_key, key, test_function)):
  141.       (e->contents == NULL_ENTRY))
  142.     {
  143.       unsigned int h2 = hsize - 2;
  144.       unsigned int incr = 1 + (hcode_initial % h2);
  145.       do
  146.         {
  147.           hcode = hcode + incr;
  148.           if (hcode >= hsize) hcode = hcode - hsize;
  149.           e = &harray [hcode];
  150.           e_key = e->key;
  151.         } 
  152.       while ((e_key)?
  153.              (KEYS_DIFFER_P (e_key, key, test_function)):
  154.              (e->contents == NULL_ENTRY));
  155.     }
  156.  
  157.   *ret_value = e->contents;
  158.   return e->key;
  159. }
  160.  
  161. void 
  162. clrhash (c_hashtable hash)
  163. {
  164.   memset (hash->harray, 0, sizeof (hentry) * hash->size);
  165.   hash->zero_entry = 0;
  166.   hash->zero_set = 0;
  167.   hash->fullness = 0;
  168. }
  169.  
  170. void
  171. free_hashtable (c_hashtable hash)
  172. {
  173. #ifdef emacs
  174.   if (!NILP (hash->elisp_table))
  175.     return;
  176. #endif
  177.   xfree (hash->harray);
  178.   xfree (hash);
  179. }
  180.  
  181. c_hashtable
  182. make_hashtable (unsigned int hsize)
  183. {
  184.   c_hashtable res = (c_hashtable) xmalloc (sizeof (struct _C_hashtable));
  185.   memset (res, 0, sizeof (struct _C_hashtable));
  186.   res->size = prime_size ((13 * hsize) / 10);
  187.   res->harray = (hentry *) xmalloc (sizeof (hentry) * res->size);
  188. #ifdef emacs
  189.   res->elisp_table = Qnil;
  190. #endif
  191.   clrhash (res);
  192.   return res;
  193. }
  194.  
  195. c_hashtable
  196. make_general_hashtable (unsigned int hsize,
  197.             unsigned long (*hash_function) (CONST void *),
  198.             int (*test_function) (CONST void *, CONST void *))
  199. {
  200.   c_hashtable res = (c_hashtable) xmalloc (sizeof (struct _C_hashtable));
  201.   memset (res, 0, sizeof (struct _C_hashtable));
  202.   res->size = prime_size ((13 * hsize) / 10);
  203.   res->harray = (hentry *) xmalloc (sizeof (hentry) * res->size);
  204.   res->hash_function = hash_function;
  205.   res->test_function = test_function;
  206. #ifdef emacs
  207.   res->elisp_table = Qnil;
  208. #endif
  209.   clrhash (res);
  210.   return res;
  211. }
  212.  
  213. c_hashtable 
  214. make_strings_hashtable (unsigned int hsize)
  215. {
  216.   return make_general_hashtable (hsize, string_hash, string_eq);
  217. }
  218.  
  219. #ifdef emacs
  220. unsigned int
  221. compute_harray_size (unsigned int hsize)
  222. {
  223.   return prime_size ((13 * hsize) / 10);
  224. }
  225. #endif
  226.  
  227. void
  228. copy_hash (c_hashtable dest, c_hashtable src)
  229. {
  230. #ifdef emacs
  231.   /* if these are not the same, then we are losing here */
  232.   if ((NILP (dest->elisp_table)) != (NILP (src->elisp_table)))
  233.     {
  234.       error ("Incompatible hashtable types to copy_hash.");
  235.       return;
  236.     }
  237. #endif
  238.  
  239.   if (dest->size != src->size)
  240.     {
  241. #ifdef emacs
  242.       if (!NILP (dest->elisp_table))
  243.         elisp_hvector_free (dest->harray, dest->elisp_table);
  244.       else
  245. #endif
  246.         xfree (dest->harray);
  247.  
  248.       dest->size = src->size;
  249. #ifdef emacs
  250.       if (!NILP (dest->elisp_table))
  251.         dest->harray = 
  252.           (hentry *) elisp_hvector_malloc
  253.             (sizeof (hentry) * dest->size, dest->elisp_table);
  254.       else
  255. #endif
  256.         dest->harray = (hentry *) xmalloc (sizeof (hentry) * dest->size);
  257.     }
  258.   dest->fullness = src->fullness;
  259.   dest->zero_entry = src->zero_entry;
  260.   dest->zero_set = src->zero_set;
  261.   dest->hash_function = src->hash_function;
  262.   dest->test_function = src->test_function;
  263.   memcpy (dest->harray, src->harray, sizeof (hentry) * dest->size);
  264. }
  265.   
  266. static void
  267. grow_hashtable (c_hashtable hash, unsigned int new_size)
  268. {
  269.   unsigned int old_hsize = hash->size;
  270.   hentry *old_harray = hash->harray;
  271.   unsigned int new_hsize = prime_size (new_size);
  272.   hentry *new_harray;
  273.  
  274. #ifdef emacs
  275.   /* We test for Qzero to facilitate free-hook.c.  That module creates
  276.      a hashtable very very early, at which point Qnil has not yet
  277.      been set and is thus all zeroes.  Qzero is "automatically"
  278.      initialized at startup because its correct value is also all
  279.      zeroes. */
  280.   if (!NILP (hash->elisp_table) && !EQ (hash->elisp_table, Qzero))
  281.     new_harray = (hentry *) elisp_hvector_malloc (sizeof (hentry) * new_hsize,
  282.                           hash->elisp_table);
  283.   else
  284. #endif
  285.     new_harray =
  286.       (hentry *) xmalloc (sizeof (hentry) * new_hsize);
  287.  
  288.   hash->size = new_hsize;
  289.   hash->harray = new_harray;
  290.  
  291.   /* do the rehash on the "grown" table */
  292.   {
  293.     long old_zero_set = hash->zero_set;
  294.     void *old_zero_entry = hash->zero_entry;
  295.     clrhash (hash);
  296.     hash->zero_set = old_zero_set;
  297.     hash->zero_entry = old_zero_entry;
  298.     rehash (old_harray, hash, old_hsize);
  299.   }
  300.  
  301. #ifdef emacs
  302.   if (!NILP (hash->elisp_table) && !EQ (hash->elisp_table, Qzero))
  303.     elisp_hvector_free (old_harray, hash->elisp_table);
  304.   else
  305. #endif
  306.     xfree (old_harray);
  307. }
  308.  
  309. void
  310. expand_hashtable (c_hashtable hash, unsigned int needed_size)
  311. {
  312.   unsigned int hsize = hash->size;
  313.   int comfortable_size = (13 * needed_size) / 10;
  314.   if (hsize < comfortable_size)
  315.     grow_hashtable (hash, comfortable_size + 1);
  316. }
  317.  
  318. void 
  319. puthash (CONST void *key, void *cont, c_hashtable hash)
  320. {
  321.   unsigned int hsize = hash->size;
  322.   int (*test_function)() = hash->test_function;
  323.   unsigned int fullness = hash->fullness;
  324.   hentry *harray;
  325.   CONST void *e_key;
  326.   hentry *e;
  327.   unsigned int hcode_initial = 
  328.     (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
  329.   unsigned int hcode;
  330.   unsigned int incr = 0;
  331.   unsigned int h2;
  332.   CONST void *oldcontents;
  333.  
  334.   if (!key) 
  335.     {
  336.       hash->zero_entry = cont;      
  337.       hash->zero_set = 1;
  338.       return;
  339.     }
  340.  
  341.   if (hsize < (1 + ((13 * fullness) / 10)))
  342.     {
  343.       grow_hashtable (hash, hsize + 1);
  344.       hsize = hash->size;
  345.       fullness = hash->fullness;
  346.     }
  347.  
  348.   harray= hash->harray;
  349.   h2 = hsize - 2;
  350.  
  351.   hcode = hcode_initial % hsize;
  352.   
  353.   e_key = harray [hcode].key;
  354.   if (e_key && (KEYS_DIFFER_P (e_key, key, test_function)))
  355.     {
  356.       h2 = hsize - 2;
  357.       incr = 1 + (hcode_initial % h2);
  358.       do
  359.         {
  360.           hcode = hcode + incr;
  361.           if (hcode >= hsize) hcode = hcode - hsize;
  362.           e_key = harray [hcode].key;
  363.         } 
  364.       while (e_key && (KEYS_DIFFER_P (e_key, key, test_function)));
  365.     }
  366.   oldcontents = harray [hcode].contents;
  367.   harray [hcode].key = key;
  368.   harray [hcode].contents = cont;
  369.   /* if the entry that we used was a deleted entry,
  370.      check for a non deleted entry of the same key,
  371.      then delete it */
  372.   if (!e_key && (oldcontents == NULL_ENTRY))
  373.     {
  374.       if (!incr) incr = 1 + ((unsigned long) key % h2);
  375.  
  376.       do
  377.         {
  378.           hcode = hcode + incr;
  379.           if (hcode >= hsize) hcode = hcode - hsize;
  380.           e = &harray [hcode];
  381.           e_key = e->key;
  382.         }
  383.       while ((e_key)?
  384.              (KEYS_DIFFER_P (e_key, key, test_function)):
  385.              (e->contents == NULL_ENTRY));
  386.  
  387.       if (e_key)
  388.         {
  389.           e->key = 0;
  390.           e->contents = NULL_ENTRY;
  391.         }
  392.     }
  393.  
  394.   /* only increment the fullness when we used up a new hentry */
  395.   if (!e_key || (KEYS_DIFFER_P (e_key, key, test_function)))
  396.     hash->fullness++;
  397. }
  398.  
  399. static void
  400. rehash (hentry *harray, c_hashtable hash, unsigned int size)
  401. {
  402.   hentry *limit = harray + size;
  403.   hentry *e;
  404.   for (e = harray; e < limit; e++)
  405.     {
  406.       if (e->key)
  407.     puthash (e->key, e->contents, hash);
  408.     }
  409. }
  410.  
  411. void 
  412. remhash (CONST void *key, c_hashtable hash)
  413. {
  414.   hentry *harray = hash->harray;
  415.   int (*test_function) (CONST void*, CONST void*) = hash->test_function;
  416.   unsigned int hsize = hash->size;
  417.   unsigned int hcode_initial = 
  418.     (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
  419.   unsigned int hcode = hcode_initial % hsize;
  420.   hentry *e = &harray [hcode];
  421.   CONST void *e_key = e->key;
  422.  
  423.   if (!key) 
  424.     {
  425.       hash->zero_entry = 0;
  426.       hash->zero_set = 0;
  427.       return;
  428.     }
  429.  
  430.   if ((e_key)?
  431.       (KEYS_DIFFER_P (e_key, key, test_function)):
  432.       (e->contents == NULL_ENTRY))
  433.     {
  434.       unsigned int h2 = hsize - 2;
  435.       unsigned int incr = 1 + (hcode_initial % h2);
  436.       do
  437.         {
  438.           hcode = hcode + incr;
  439.           if (hcode >= hsize) hcode = hcode - hsize;
  440.           e = &harray [hcode];
  441.           e_key = e->key;
  442.         }
  443.       while ((e_key)?
  444.              (KEYS_DIFFER_P (e_key, key, test_function)):
  445.              (e->contents == NULL_ENTRY));
  446.     }
  447.   if (e_key)
  448.     {
  449.       e->key = 0;
  450.       e->contents = NULL_ENTRY;
  451.       /* Note: you can't do fullness-- here, it breaks the world. */
  452.     }
  453. }
  454.  
  455. void 
  456. maphash (maphash_function mf, c_hashtable hash, void *arg)
  457. {
  458.   hentry *e;
  459.   hentry *limit;
  460.   
  461.   if (hash->zero_set) 
  462.     ((*mf) (0, hash->zero_entry, arg));
  463.  
  464.   for (e = hash->harray, limit = e + hash->size; e < limit; e++)
  465.     {
  466.       if (e->key)
  467.     ((*mf) (e->key, e->contents, arg));
  468.     }
  469. }
  470.  
  471. void 
  472. map_remhash (remhash_predicate predicate, c_hashtable hash, void *arg)
  473. {
  474.   hentry *e;
  475.   hentry *limit;
  476.   
  477.   if (hash->zero_set && ((*predicate) (0, hash->zero_entry, arg)))
  478.     {
  479.       hash->zero_set = 0;
  480.       hash->zero_entry = 0;
  481.     }
  482.  
  483.   for (e = hash->harray, limit = e + hash->size; e < limit; e++)
  484.     if ((*predicate) (e->key, e->contents, arg))
  485.       {
  486.         e->key = 0;
  487.         e->contents = NULL_ENTRY;
  488.       }
  489. }
  490.